package com.LeeCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 最多可以参加的会议数目
 */

public class Code1353 {
    public static void main(String[] args) {
        int[][] events = {
                {1, 2},
                {1, 2},
                {3, 3},
                {1, 5},
                {1, 5}
        };
        System.out.println(new Code1353().maxEvents1(events));
    }

    public int maxEvents(int[][] events) {
        int mx = 0;
        for (int[] e : events) {
            mx = Math.max(mx, e[1]);
        }

        List<Integer>[] groups = new ArrayList[mx + 1];
        Arrays.setAll(groups, i -> new ArrayList<>());
        for (int[] e : events) {
            groups[e[0]].add(e[1]);
        }

        int ans = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i <= mx; i++) {
            while (!pq.isEmpty() && pq.peek() < i) {
                pq.poll();
            }
            for (int endTime : groups[i]) {
                pq.add(endTime);
            }

            if (!pq.isEmpty()) {
                ans++;
                pq.poll();
            }
        }

        return ans;
    }

    public int maxEvents1(int[][] events) {
        Arrays.sort(events, (a, b) -> a[1] - b[1]);

        int mx = events[events.length - 1][1];
        int[] fa = new int[mx + 2];
        for (int i = 0; i < fa.length; i++) {
            fa[i] = i;
        }

        int ans = 0;
        for (int[] e : events) {
            int x = find(e[0], fa); // 查找从 startDay 开始的第一个可用天
            if (x <= e[1]) {
                ans++;
                fa[x] = x + 1; // 标记 x 已占用
            }
        }
        return ans;
    }

    // f(i) = i 表示未占用
    private int find(int x, int[] fa) {
        if (fa[x] != x) {

            // 压缩路径
            fa[x] = find(fa[x], fa);
        }
        return fa[x];
    }
}
